/*
 * @lc app=leetcode.cn id=34 lang=swift
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        let left = leftRange(nums, target)
        if left == -1 {
            return [-1, -1]
        }
        let right = rightRange(nums, target)
        return [left, right]
    }

    func leftRange(_ nums: [Int], _ target: Int) -> Int {
        var left = 0, right = nums.count - 1
        while left <= right {
            let middle = (left + right) / 2
            if nums[middle] > target {
                right = middle - 1
            } else if nums[middle] < target {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        if left > nums.count - 1 || nums[left] != target {
            return -1
        }
        return left
    }

    func rightRange(_ nums: [Int], _ target: Int) -> Int {
        var left = 0, right = nums.count - 1
        while left <= right {
            let middle = (left + right) / 2
            if nums[middle] > target {
                right = middle - 1
            } else if nums[middle] < target {
                left = middle + 1
            } else {
                left = middle + 1
            }
        }
        if right < 0 || nums[right] != target {
            return -1
        }
        return right
    }
}
// @lc code=end

